import sys

def decodeItem (charlist):
	if len(charlist) < 1:
		return;

	if charlist[-1] == "i":
		charlist.pop()
		return decodeInteger( charlist )		
		
	elif charlist[-1].isdigit():
		return decodeString( charlist )

	elif charlist[-1] == "l":
		charlist.pop()
		return decodeList( charlist )
		
	elif charlist[-1] == "d":
		charlist.pop()
		return decodeDict( charlist )

	else:
		print "char was " + charlist[-1] + " - does not compute"
		charlist.reverse()
		print "".join( charlist )
		print len(charlist)
		sys.exit()



def decodeString (charlist):
	charCount = ""
	string = ""
	
	while charlist[-1] != ":":
		charCount += charlist.pop()				
	charlist.pop()
	
	charCount = int(charCount)

	string = charlist[-charCount:]
	string.reverse()
	string = "".join( string )

	del charlist[-charCount:]

	return string


def decodeInteger (charlist):
	integer = ""
	
	while charlist[-1] != "e":
		integer += charlist.pop()
	charlist.pop()

	return int(integer)

		
def decodeList (charlist):
	contents = [];
	
	while charlist[-1] != "e":
		contents.append( decodeItem(charlist) )
	charlist.pop()

	return contents


def decodeDict (charlist):
	dictionary = {}
	
	while (charlist[-1] != "e"):
		key = decodeItem( charlist )
		item = decodeItem( charlist )
		dictionary[key] = item		
	charlist.pop()
	
	return dictionary

	
	
	
	
	


def bencode (item):
	if isinstance(item, int) or isinstance(item, long):
		return  bencodeInteger(item)
	elif isinstance(item, str):
		return bencodeString(item)
	elif isinstance(item, list):
		return bencodeList(item)
	elif isinstance(item, dict):
		return bencodeDict(item)
	else:
		print "Bencode Fail! - " + str(item) + " type is unrecognized"
		sys.exit()


def bencodeInteger (integer):
	return "i" + str(integer) + "e"


def bencodeString (string):
	return str(len(string)) + ":" + string


def bencodeList (itemList):
	bencoding = "l"
	
	for item in itemList:
		bencoding += bencode(item)
		
	bencoding += "e"
	return bencoding
	

def bencodeDict (dictionary):
	bencoding = "d"
	
	itemList = dictionary.items()
	itemList.sort()

	for key, value in itemList:
		bencoding += bencode(key)
		bencoding += bencode(value)
	
	bencoding += "e"
	return bencoding

	

	
